#ifndef __IM_LIST_H__
#define __IM_LIST_H__

#include <im_base_types.h>
/**
 * @defgroup IMList
 * @ingroup PrivateIMBusIME
 * @{
 */

/** @struct IMList
 *  @brief Doubly linked list
 */

IM_BEGIN_DECLS

typedef struct _IMList IMList;

struct _IMList
{
    IMPointer data;
    IMList *next;
    IMList *prev;
};


/**
 * @brief   Allocates space for one IMList element.
 *
 * It is called by im_list_append(), im_list_prepend(), im_list_insert() and
 * im_list_insert_sorted() and so is rarely used on its own.
 *
 * @returns a newly-allocated IMList element.
 */
IMList*     im_list_alloc                   (void) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Frees all of the memory used by an IMList.
 * @note    If list elements contain dynamically-allocated memory, they should
 *          be freed first.
 *
 * @param   list    an IMList.
 */
void        im_list_free                    (IMList            *list);

/**
 * @brief   Frees one IMList element.
 *
 * This is usually used after im_list_remove_link().
 *
 * @param   list    an IMList.
 */
void        im_list_free_node               (IMList            *list);

/**
 * @brief   Adds a new element on to the end of the list.
 * @note    The return value is the new start of the list, which may have
 *          changed, so make sure you store the new value.
 * @note    im_list_append() has to traverse the entire list to find the end,
 *          which is inefficient when adding multiple elements. A common idiom
 *          to avoid the inefficiency is to prepend the elements and reverse
 *          the list when all elements have been added.
 *
 * @param   list    an IMList.
 * @param   data    the data for the new element.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_append                  (IMList            *list,
                                             IMPointer          data) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Adds a new element on to the start of the list.
 * @note    The return value is the new start of the list, which may have
 *          changed, so make sure you store the new value.
 *
 * @param   list    an IMList.
 * @param   data    the data for the new element.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_prepend                 (IMList            *list,
                                             IMPointer          data) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Inserts a new element into the list at the given position.
 *
 * @param   list    an IMList.
 * @param   data    the data for the new element.
 * @param   position  the position to insert the element. If this is negative,
 *                  or is larger than the number of elements in the list, the
 *                  new element is added on to the end of the list.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_insert                  (IMList            *list,
                                             IMPointer          data,
                                             IMInt              position) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Inserts a new element into the list, using the given comparison
 *          function to determine its position.
 *
 * @param   list    an IMList.
 * @param   data    the data for the new element.
 * @param   func    the function to compare elements in the list. It should
 *                  return a number > 0 if the first parameter comes after the
 *                  second parameter in the sort order.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_insert_sorted           (IMList            *list,
                                             IMPointer          data,
                                             IMCompareFunc      func) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Inserts a new element into the list, using the given comparison
 *          function to determine its position.
 *
 * @param   list    an IMList.
 * @param   data    the data for the new element.
 * @param   func    the function to compare elements in the list. It should
 *                  return a number > 0 if the first parameter comes after the
 *                  second parameter in the sort order.
 * @param   user_data   user data to pass to comparison function.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_insert_sorted_with_data (IMList            *list,
                                             IMPointer          data,
                                             IMCompareDataFunc  func,
                                             IMPointer          user_data) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Inserts a new element into the list before the given position.
 *
 * @param   list    an IMList.
 * @param   sibling the list element before which the new element is inserted
 *                  or NULL to insert at the end of the list.
 * @param   data    the data for the new element.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_insert_before           (IMList            *list,
                                             IMList            *sibling,
                                             IMPointer          data) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Adds the second IMList onto the end of the first IMList.
 * @note    The elements of the second IMList are not copied. They are used
 *          directly.
 *
 * @param   list1   an IMList.
 * @param   list2   the IMList to add to the end of the first IMList.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_concat                  (IMList            *list1,
                                             IMList            *list2) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Removes an element from an IMList.
 *
 * If two elements contain the same data, only the first is removed. If none of
 * the elements contain the data, the IMList is unchanged.
 *
 * @param   list    an IMList.
 * @param   data    the data of the element to remove.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_remove                  (IMList            *list,
                                             IMConstPointer     data) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Removes all list nodes with data equal to data.
 * @see     im_list_remove()
 *
 * @param   list    an IMList.
 * @param   data    data to remove.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_remove_all              (IMList            *list,
                                             IMConstPointer     data) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Removes an element from an IMList, without freeing the element.
 *
 * The removed element's prev and next links are set to NULL, so that it
 * becomes a self-contained list with one element.
 *
 * @param   list    an IMList.
 * @param   link    an element in the IMList.
 *
 * @returns the new start of the IMList, with link removed.
 */
IMList*     im_list_remove_link             (IMList            *list,
                                             IMList            *link) IM_GNUC_WARN_UNUSED_RESULT;
/**
 * @brief   Deletes the node link from list.
 *
 * @param   list    an IMList.
 * @param   link    node to delete from list.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_delete_link             (IMList            *list,
                                             IMList            *link) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Reverses an IMList.
 *
 * It simply switches the next and prev pointers of each element.
 *
 * @param   list    an IMList.
 *
 * @returns the new start of the IMList.
 */
IMList*     im_list_reverse                 (IMList            *list) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Clones an IMList.
 * @note    This is a "shallow" copy. If the list elements consist of pointers
 *          to data, the pointers are copied but the actual data isn't.
 *
 * @param   list    an IMList.
 *
 * @returns a clone of the IMList.
 */
IMList*     im_list_clone                   (IMList            *list) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Gets the element at the given position in an IMList.
 *
 * @param   list    an IMList.
 * @param   n       the position of the element, counting from 0.
 *
 * @returns the element, or NULL if the position is off the end of the IMList.
 */
IMList*     im_list_nth                     (IMList            *list,
                                             IMUInt             n);

/**
 * @brief   Gets the element n places before list.
 *
 * @param   list    an IMList.
 * @param   n       the position of the element, counting from 0.
 *
 * @returns the element, or NULL if the position is off the end of the IMList.
 */
IMList*     im_list_nth_prev                (IMList            *list,
                                             IMUInt             n);

/**
 * @brief   Finds the element in an IMList which contains the given data.
 *
 * @param   list    an IMList.
 * @param   data    the element data to find.
 *
 * @returns the found IMList element, or NULL if it is not found.
 */
IMList*     im_list_find                    (IMList            *list,
                                             IMConstPointer     data);

/**
 * @brief   Finds an element in an IMList, using a supplied function to find
 *          the desired element.
 *
 * It iterates over the list, calling the given function which should return 0
 * when the desired element is found.
 *
 * @param   list    an IMList.
 * @param   data    user data passed to func.
 * @param   func    the function to call for each element. It should return 0
 *                  when the desired element is found.
 *
 * @returns the found IMList element, or NULL if it is not found.
 */
IMList*     im_list_find_custom             (IMList            *list,
                                             IMConstPointer     data,
                                             IMCompareFunc      func);

/**
 * @brief   Gets the position of the given element in the IMList, starting from
 *          0.
 *
 * @param   list    an IMList.
 * @param   link    an element in the IMList.
 *
 * @returns the position of the element in the IMList, or -1 if the element is
 *          not found.
 */
IMInt       im_list_position                (IMList            *list,
                                             IMList            *link);

/**
 * @brief   Gets the position of the element containing the given data,
 *          starting from 0.
 *
 * @param   list    an IMList.
 * @param   data    the data to find.
 *
 * @returns the index of the element containing the data, or -1 if the data is
 *          not found.
 */
IMInt       im_list_index                   (IMList            *list,
                                             IMConstPointer     data);

/**
 * @brief   Gets the last element in an IMList.
 *
 * @param   list    an IMList.
 *
 * @returns the last element in the IMList, or NULL if the IMList has no elements.
 */
IMList*     im_list_last                    (IMList            *list);

/**
 * @brief   Gets the first element in an IMList.
 *
 * @param   list    an IMList.
 *
 * @returns the first element in an IMList, or NULL if the IMList has no elements.
 */
IMList*     im_list_first                   (IMList            *list);

/**
 * @brief   Gets the number of elements in an IMList.
 *
 * @param   list    an IMList.
 *
 * @returns the number of elements in the IMList.
 */
IMUInt      im_list_length                  (IMList            *list);

/**
 * @brief   Calls a function for each element of an IMList.
 *
 * @param   list    an IMList.
 * @param   func    the function to call with each element's data.
 * @param   user_data   user data to pass to func.
 */
void        im_list_foreach                 (IMList            *list,
                                             IMFunc             func,
                                             IMPointer          user_data);

/**
 * @brief   Sorts an IMList using the given comparison function.
 *
 * @param   list    an IMList.
 * @param   compare_func    the comparison function used to sort the IMList.
 *                  This function is passed the data from 2 elements of the
 *                  IMList and should return 0 if they are equal, a negative
 *                  value if the first element comes before the second, or a
 *                  positive value if the first element comes after the second.
 *
 * @returns the new start of the sorted IMList.
 */
IMList*     im_list_sort                    (IMList            *list,
                                             IMCompareFunc      compare_func) IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Sorts an IMList using the given comparison function and user data.
 *
 * @param   list    an IMList.
 * @param   compare_func    the comparison function used to sort the IMList.
 *                  This function is passed the data from 2 elements of the
 *                  IMList and should return 0 if they are equal, a negative
 *                  value if the first element comes before the second, or a
 *                  positive value if the first element comes after the second.
 * @param   user_data   user data to pass to compare_func.
 *
 * @returns the new start of the sorted IMList.
 */
IMList*     im_list_sort_with_data          (IMList            *list,
                                             IMCompareDataFunc  compare_func,
                                             IMPointer          user_data)  IM_GNUC_WARN_UNUSED_RESULT;

/**
 * @brief   Gets the data of the element at the given position.
 *
 * @param   list    an IMList.
 * @param   n       the position of the element.
 *
 * @returns the element's data, or NULL if the position is off the end of the IMList.
 */
IMPointer   im_list_nth_data                (IMList            *list,
                                             IMUInt             n);

/**
 * @brief   A convenience macro to gets the previous element in an IMList.
 *
 * @param   list    an IMList.
 *
 * @returns the previous element, or NULL if there are no previous elements.
 */
#define     im_list_previous(list)          ((list) ? (((IMList *)(list))->prev) : NULL)

/**
 * @brief   A convenience macro to gets the next element in an IMList.
 *
 * @param   list    an IMList.
 *
 * @returns the next element, or NULL if there are no more elements.
 */
#define     im_list_next(list)              ((list) ? (((IMList *)(list))->next) : NULL)

IM_END_DECLS
/** @} */

#endif
/*
vi:ts=4:nowrap:ai:expandtab
*/
